package com.lw.leetcode.dp.c;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 2035. 将数组分成两个数组并最小化数组和的差
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/6 15:48
 */
public class MinimumDifference {

    public int minimumDifference(int[] nums) {
        int length = nums.length;
        int l = length >> 1;
        Set<Integer>[] sets1 = new HashSet[l + 1];
        TreeSet<Integer>[] sets2 = new TreeSet[l + 1];
        for (int i = 1; i <= l; i++) {
            sets1[i] = new HashSet<>();
            sets2[i] = new TreeSet<>();
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int m = sum >> 1;
        int end = 1 << l;
        int[] arr = new int[end];

        int min = Integer.MAX_VALUE;
        for (int i = 1; i < end; i++) {
            int v = i & (i - 1);
            arr[i] = arr[v] + nums[Integer.bitCount(i - v - 1)];
            sets1[Integer.bitCount(i)].add(arr[i]);
        }
        for (int i = 1; i < end; i++) {
            int v = i & (i - 1);
            arr[i] = arr[v] + nums[l + Integer.bitCount(i - v - 1)];
            sets2[Integer.bitCount(i)].add(arr[i]);
        }
        Set<Integer> set = sets1[l];
        for (Integer v : set) {
            min = Math.min(min, Math.abs(sum - (v << 1)));
        }
        set = sets2[l];
        for (Integer v : set) {
            min = Math.min(min, Math.abs(sum - (v << 1)));
        }
        for (int i = 1; i < l; i++) {
            Set<Integer> set1 = sets1[i];
            TreeSet<Integer> set2 = sets2[l - i];
            for (int v1 : set1) {
                int v2 = m - v1;
                Integer floor = set2.floor(v2);
                if (floor != null) {
                    int s = v1 + floor;
                    min = Math.min(min, sum - (s << 1));
                }
                v2++;
                floor = set2.floor(v2);
                if (floor != null) {
                    int s = v1 + floor;
                    min = Math.min(min, Math.abs(sum - (s << 1)));
                }
            }
        }
        return min;
    }

}
